Graphes III : Plus courts chemins dans des graphes pondérés

Table des matières

1. Préliminaires

1.1. Graphe pondéré

Un graphe pondéré est un graphe dans lequel un poids est associé à chaque arête. En pratique, ces poids représentent des distances ou durées.

Si $s_1 \ra s_2 \ra \dots \ra s_n$ est un chemin dans un graphe pondéré, le poids du chemin est la somme des poids des arêtes $s_1\ra s_2$, $s_2 \ra s_3$, …, $s_{n-1}\ra s_n$.

La distance entre deux sommets $i,j$, notée $d(i,j)$, est le poids minimal d'un chemin de $i$ à $j$ dans le graphe.

Dans le graphe ci-contre, la distance entre Marseille et Strasbourg est de 5h15.

Représentation en Python

On peut représenter un graphe pondéré

  1. Par une matrice d'adjacence pondérée M, où M[i][j] vaut p s'il existe une arête $i\ra j$ de poids p, ou None s'il n'existe pas d'arête de $i$ à $j$.
  2. Par des listes d'adjacence pondérées, par exemple dans une liste de listes L, où L[i] est une liste de couples (j, p) et $(j,p)\in \texttt{L[i]}$ signifie qu'une arête de poids $p$ relie $i$ à $j$.

Écrire une fonction poids_chemin qui prend en argument un graphe $G$ et un chemin éventuel sur $G$, représenté par une liste de sommets de $G$ et qui renvoie le poids total du chemin, ou None, si la liste de sommets donnée ne représente pas un chemin.

  1. Si $G$ est représenté par une matrice d'adjacence pondérée.
  2. Si $G$ est représenté par une liste de listes d'adjacence pondérées.

2. Algorithme de Dijkstra

L'algorithme de Dijkstra détermine un chemin de poids minimal entre un sommet initial $i$ et un sommet final $f$ d'un graphe pondéré.

Il consiste en un parcours du graphe au cours duquel on va remplir un tableau distance qui contiendra finalement toutes les distances de $i$ à chaque sommet du graphe. Le tableau distance peut-être initialisé à [None] * len(G). Au fil du parcours, distance[s] est ce qu'on pense être la longueur du plus court chemin de $i$ à $s$, étant donné les sommets que l'on a traités.

On traitera les sommets du graphe dans l'ordre de leur distance à $i$. Pour cela on utilisera une variable a_traiter qui représentera une file de priorité, contenant des sommets $s$ du graphe, avec comme poids la distance entre $i$ et $s$ (contrainte à ne passer que par les sommets déjà traités), que l'on mettra à jour au fil du parcours.

Décrire l'exécution de l'algorithme de Dijkstra sur le graphe suivant, pour trouver un chemin de poids minimal de $A$ à $H$.

La file de priorité a_traiter sera implémentée, au choix,

  • Par un dictionnaire sommet -> priorité, et l'utilisation d'une fonction retire_min qui renvoie le couple (s, p) de priorité minimale (et le retire du dictionnaire), que l'on ne demande pas d'implémenter.
  • Par le module PriorityQueue de Python, qui s'utilise comme illustré ci-contre. Attention, ce module ne permet pas de mettre à jour la priorité d'une donnée déjà présente. Si nécessaire, on peut ajouter un second exemplaire de la donnée, avec une autre priorité.

Il n'est pas utile de maintenir un ensemble vus des sommets vus. Par contre, on peut éventuellement utiliser un ensemble traités des sommets traités. 

from queue import PriorityQueue
q = PriorityQueue() # File vide
q.put((2, 'abc'))   # Élément 'abc',
                    # priorité de 2.
q.put((4, 'efg'))

while not q.empty():
    # On récupère l'élément de plus
    # petite priorité, et le retire
    # de la file
    (priority, next_item) = q.get()
    print(next_item)

  1. Quand les poids sont tous égaux, l'algorithme de Dijkstra revient à un parcours du graphe en largeur.
  2. L'algorithme de Dijkstra détermine, petit à petit, toutes les distances du sommet initial aux autres sommets, jusqu'à traiter le sommet final recherché.

On peut se contenter de ne mettre à jour le tableau distance[s] uniquement quand on traite le sommet $s$.

  1. Implémenter l'algorithme de Dijkstra, sous la forme d'une fonction prenant en argument un graphe pondéré, représenté par ses listes d'adjacence pondérées, un sommet initial $d$, et qui renvoie le tableau distance des distances de $d$ à chaque sommet du graphe.
  2. En utilisant un tableau parent initialisé à [None] * len(G), qui est complété au fil du parcours de sorte que parent[s] soit le sommet précédant $s$ dans le plus court chemin de $i$ à $s$, écrire une version qui renvoie un plus court chemin entre deux sommets.

Lorsque le sommet $s$ est traité, sa priorité est la distance de $i$ à $s$.

Par récurrence sur le nombre de sommets traités. Le premier sommet traité est le sommet d, pour lequel cette propriété est correcte.

On suppose qu'à un instant donné, on s’apprête à traiter le sommet $s$, et que cette propriété était valable pour tous les sommets déjà traités, dont on note $\mc T$ l'ensemble.

Tout élément $f$ de la file de priorité est issu d'un sommet $t$ qui a été traité, et a une priorité qui vaut $d(i, t) + p_{t\ra f}$.

C'est en particulier le cas de $s$, qui provient d'une arête $s_t \ra s$ de poids $p$. D'après la propriété de la file de priorité, cette arête $s_t \ra s$ est celle qui minimise la quantité $d(i, s_t) + p$, parmi toutes les arêtes issues d'un des sommets traités et allant vers un sommet non traité. Cela implique que $d(i, s_t) + p$ est bien la distance $d(i, s)$ (puisque tout chemin de $i$ à $s$ qui quitte $\mc T$ avant aura un poids supérieur).

L'algorithme de Dijkstra parcourt le graphe au plus une fois, au sens où chaque arête du graphe n'est considérée qu'au plus une fois. Les instructions de la boucle intérieure sont donc exécutées au plus $m$ fois, et elles ont une complexité en $O(1)$. D'autre part, l'instruction retire_min est exécutée au plus $n$ fois (une fois par sommet du graphe). Avec notre implémentation naïve d'une file de priorité, elle a une complexité en $O(n)$, ce qui donne une complexité totale en $O(n^2 + m) = O(n^2)$. Avec une implémentation efficace d'une file de priorité, on obtient une complexité en $O(n\ln n + m)$.

  1. Écrire une fonction distance_maximale qui prend en argument un graphe et un sommet initial $i$ et qui renvoie un couple $(f, d)$ où $f$ est un sommet du graphe à une distance maximale de $i$ et $d$ est cette distance.
  2. Le diamètre d'un graphe est défini comme $\max\limits_{i,j\in S} d(i,j)$. Écrire une fonction diamètre qui prend en argument un graphe et renvoie son diamètre.

Soit $G$ un graphe pondéré avec $\db{0,n-1}$ comme ensemble de sommets.

Pour $i, j, k\in \db{0,n-1}$, on note $d_{k}(i,j)$ la longueur du plus court chemin de $i$ à $j$, dont tous les sommets intermédiaires appartiennent à $\db{0,k}$.

On note également $d_{-1}(i, j)$ le poids de l'arête $i\ra j$ si elle existe, ou None sinon.

  1. Justifier que pour $k\geq 0$, $$d_k(i,j) = \min \big(d_{k-1}(i,j),\, d_{k-1}(i, k) + d_{k-1}(k, j)\big).$$
  2. En utilisant ce qui précède, implémenter un algorithme en $O(n^3)$ qui calcule une matrice $D$ telle que $D_{ij}$ soit la longueur du plus court chemin entre $i$ et $j$. On pourra supposer que le graphe est représenté par sa matrice d'adjacence.

3. Algorithme $A^*$

Pour trouver le plus court chemin entre deux points du réseau routier français, l'algorithme de Dijkstra (qui est fondamentalement un parcours en largeur) serait très inefficace.

On peut imaginer pouvoir faire mieux en guidant la recherche de sorte à préférer les routes qui vont dans la bonne direction.

L'algorithme $A^*$ est une variante rapide de l'algorithme de Dijkstra quand on dispose d'une heuristique $h$ permettant d'estimer a priori la distance entre deux sommets.

Dans l'exemple d'un réseau routier, on peut prendre comme heuristique la fonction $h$ qui à deux points associe la distance à vol d'oiseau entre ces deux points.

La structure de l'algorithme $A^*$ pour trouver le plus court chemin entre $i$ et $s$ est la même que celle de l'algorithme de Dijkstra, mais dans a_traiter, au lieu de pondérer un sommet $s$ par $d(i, s)$, on le pondère par $d(i, s) + h(s, f)$.

routes_france.png

Décrire l'exécution de l'algorithme $A^*$ sur le graphe suivant, pour trouver un chemin de poids minimal de $A$ à $D$. Les poids des arêtes sont les distances euclidiennes entre les points.

On suppose que les sommets de $G$ correspondent à des points du plan euclidien, et que cette correspondance est donnée par une liste l_coord telle que l_coord[i] soit le couple (x,y) des coordonnées du sommet i.

Écrire une fonction distance_eucl qui prend en argument deux sommets du graphe et la liste l_coord et qui renvoie la distance euclidienne entre les deux sommets.

Implémenter l'algorithme $A^*$, sous la forme d'une fonction prenant en argument le graphe, la fonction heuristique $h$ et deux sommets, et qui renvoie la distance entre les deux sommets.

Étant donné un sommet final $f$, on dit qu'une heuristique $h$ est

  • admissible si $\forall s,\, h(s,f)\leq d(s,f)$. Autrement dit, l'heuristique sous-estime la distance au sommet final.
  • monotone si pour tous sommets $h(s_1, f) \leq d(s_1, s_2) + h(s_2, f)$, et $h(f, f) = 0$. C'est une forme d'inégalité triangulaire.

La monotonie implique l'admissibilité.

L'heuristique euclidienne sur une carte plane est monotone.

Si l'heuristique est monotone alors l'algorithme $A^*$ renvoie un plus court chemin de $i$ à $f$, avec une complexité en $O(m + n \ln n)$ dans le pire des cas.

Si l'heuristique est bonne, la complexité est meilleure en pratique.

Si l'heuristique est seulement admissible, une version modifiée de l'algorithme $A^*$, garantit de trouver un plus court chemin, mais sa complexité pourrait être non polynomiale.

En pratique, l'algorithme $A^*$ est souvent utilisé pour trouver rapidement des chemins assez court, sans se soucier de l'optimalité.

4. Correction de l'algorithme $A^*$

A*, version efficace

def A_étoile(g, h, i, f):
    a_traiter = {i: h(i,f)}
    distance = [None] * len(g)  # Sert à savoir quels sommets ont été traités
    while len(a_traiter) != 0:
        (s, d) = retire_min(a_traiter) # d est la distance de i à s + h(s,f)
        distance[s] = d - h(s, f)
        if s == f:
            return distance[s]
        for (v, pa) in g[s]:      # pa est le poids de l'arête s→ v
            nd = distance[s] + pa # La distance de i à v, en passant par s
            ndh = nd + h(v,f)     # distance + heuristique
            # Si v n'a pas encore été traité, et ou bien n'a jamais
            # été vu, ou bien a été vu avec une plus grande priorité
            if distance[v] is None and (v not in a_traiter or a_traiter[v] > ndh):
                a_traiter[v] = ndh # On rajoute v à la file de priorité

Par rapport à l'algorithme de Dijkstra, l'algorithme de A* utilise l'heuristique pour restreindre les possibilités et réduire l'ensemble des sommets visités.

Dans le pire des cas (si l'heuristique n'apporte rien), cette version de A* a une complexité en $O(m + n \ln n)$, comme l'algorithme de Dijktsra.

Cet algorithme est garanti de trouver la distance de $i$ à $f$ selon un chemin optimal si l'heuristique $h$ est monotone.

La monotonie permet de garantir qu'au moment où l'on traite un sommet $s$, on a bien trouvé le plus court chemin de $i$ à $s$.

A*, version non monotone

Pour une heuristique non monotone, mais admissible, la version suivante de A* garantit de trouver le plus court chemin de $i$ à $s$, mais sa complexité n'est plus polynomiale dans le pire des cas. Elle consiste à retraiter les sommets déjà traités, si on les retrouve avec un plus court chemin. 

def A_étoile(g, h, i, f):
    a_traiter = {i: h(i,f)}
    distance = [None] * len(g)
    while len(a_traiter) != 0:
        (s, d) = retire_min(a_traiter)
        distance[s] = d - h(s, f)
        if s == f:
            return distance[s]
        for (v, pa) in g[s]:      # pa est le poids de l'arête s→ v
            nd = distance[s] + pa
            ndh = nd + h(v,f)     # distance + heuristique
            # Si v n'a pas encore été traité, ou si v avait déjà été
            # traité, mais on a à présent trouver un plus court chemin
            # de i à v. Alors il faut retraiter v, et il faudra
            # retraiter tous ses successeurs.
            if (distance[v] is None or nd < distance[v]) and \
               (v not in a_traiter or a_traiter[v] > ndh):
                a_traiter[v] = ndh # On rajoute v à la file de priorité

L'admissibilité garantit que lorsque l'on s'arrête, on a bien trouvé le plus court chemin.

En pratique, l'algorithme A* est utilisé pour trouver rapidement un chemin «assez court», sans avoir besoin de garantir l'optimalité. On utilise donc plutôt la première version, éventuellement avec des heuristiques volontairement non admissibles qui excluent le plus de branchements possibles.